| 1. |
- Qian, Yue, et al.
(författare)
-
Analysis of Communication Delay Bounds for Network on Chips
- 2009
-
Ingår i: PROCEEDINGS OF THE ASP-DAC 2009. - 9781424427482 ; , s. 7-12
-
Konferensbidrag (refereegranskat)abstract
- In network-on-chip, computing worst-case delay bound for packet delivery is crucial for designing predictable systems but yet an intractable problem due to complicated resource contention scenarios. In this paper, we present an analysis technique to derive the communication delay bound for individual flows. Based on a network contention model, this technique, which is topology independent, employs the network calculus theory to first compute the equivalent service curve for individual flows and then calculate their packet delay bound. To exemplify our method, we also present the derivation of a closed-form formula to calculate the delay bound for all-to-one gather communication. Our experimental results demonstrate the theoretical bounds are correct and tight.
|
|
| 2. |
- Qian, Yue, et al.
(författare)
-
Analysis of Worst-case Delay Bounds for Best-effort Communication in Wormhole Networks on Chip
- 2009
-
Ingår i: 2009 3RD ACM/IEEE INTERNATIONAL SYMPOSIUM ON NETWORKS-ON-CHIP. - 9781424441433 ; , s. 44-53
-
Konferensbidrag (refereegranskat)abstract
- In packet-switched network-on-chip, computing worst-case delay bounds is crucial for designing predictable and cost-effective communication systems but yet an intractable problem due to complicated resource sharing scenarios. For wormhole networks with credit-based flow control, the existence of cyclic dependency between flit delivery and credit generation further complicates the problem. Based on network calculus, we propose a technique for analyzing communication delay bounds for individual flows in wormhole networks. We first propose router service analysis models for flow control, link and buffer sharing. Based on these analysis models, we obtain a buffering-sharing analysis network, which is open-ended and captures both flow control and link sharing. Furthermore, we compute equivalent service curves for individual flows using the network contention tree model in the buffer-sharing analysis network, and then derive their delay bounds. Our experimental results verify that the theoretical bounds are correct and tight.
|
|
| 3. |
- Qian, Yue, et al.
(författare)
-
Analysis of Worst-Case Delay Bounds for On-Chip Packet-Switching Networks
- 2010
-
Ingår i: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 0278-0070 .- 1937-4151. ; 29:5, s. 802-815
-
Tidskriftsartikel (refereegranskat)abstract
- In network-on-chip (NoC), computing worst-case delay bounds for packet delivery is crucial for designing predictable systems but yet an intractable problem. This paper presents an analysis technique to derive per-flow communication delay bound. Based on a network contention model, this technique, which is topology independent, employs network calculus to first compute the equivalent service curve for an individual flow and then calculate its packet delay bound. To exemplify this method, this paper also presents the derivation of a closed-form formula to compute a flow's delay bound under all-to-one gather communication. Experimental results demonstrate that the theoretical bounds are correct and tight.
|
|
| 4. |
- Qian, Yue, et al.
(författare)
-
Analyzing Credit-Based Router-to-Router Flow Control for On-Chip Networks
- 2009
-
Ingår i: IEICE transactions on electronics. - 0916-8524 .- 1745-1353. ; E92C:10, s. 1276-1283
-
Tidskriftsartikel (refereegranskat)abstract
- Credit-based router-to-router flow control is one main link-level flow control mechanism proposed for Networks on Chip (NoCs). Based on network calculus, we analyze its performance and optimal buffer size. To model the feedback control behavior due to credits, we introduce a virtual network service element called flow controller. Then we derive its service curve, and further the system service curve. In addition, we give and prove a theorem that determines the optimal buffer size guaranteeing the maximum system service curve. Moreover, assuming the latency-rate server model for routers, we give closed-form formulas to calculate the flit delay bound and optimal buffer size. Our experiments with real on-chip traffic traces validate that our analysis is correct; delay bounds are tight and the optimal buffer size is exact.
|
|
| 5. |
- Qian, Yue, et al.
(författare)
-
Applying Network Calculus for Performance Analysis of Self-Similar Traffic in On-Chip Networks
- 2009
-
Ingår i: IEEE/ACM/IFIP 2009 International Conference on Hardware-Software Codesign and System Synthesis (CODES+ISSS’09). - New York, NY, USA : ACM. - 9781605586281 ; , s. 453-460
-
Konferensbidrag (refereegranskat)abstract
- On-chip traffic of many applications exhibits self-similar characteristics. In this paper, we intend to apply network calculus to analyze the delay and backlog bounds for self-similar traffic in networks on chips. We first prove that self-similar traffic can not be constrained by any deterministic arrival curve. Then we prove that self-similar traffic can be constrained by deterministic linear arrival curves α{r,b}(t)=rt+b (r:rate, b:burstiness) if an additional parameter, excess probability ε, is used to capture its burstiness exceeding the arrival envelope. This three-parameter model, ε-α{r,b}(t)=rt+b(ε), enables us to apply and extend the results of network calculus to analyze the performance and buffering cost of networks delivering self-similar traffic flows. Assuming the latency-rate server model for the network elements, we give closed-form equations to compute the delay and backlog bounds for self-similar traffic traversing a series of network elements. Furthermore, we describe a performance analysis flow with self-similar traffic as input. Our experimental results using real on-chip multimedia traffic traces validate our model and approach.
|
|
| 6. |
- Qian, Yue, et al.
(författare)
-
Applying Network Calculus for Worst-case Delay Bound Analysis in On-chip Networks
- 2009
-
Ingår i: Proceedings of the DTIS'09 - 2009 4th IEEE International Conference on Design and Technology of Integrated Systems in Nanoscale Era. - 9781424443208 ; , s. 113-118
-
Konferensbidrag (refereegranskat)abstract
- In network-on-chip, computing worst-case delay bounds for packet delivery is crucial for designing predictable systems but yet an intractable problem due to complicated resource contention scenarios. In this paper, based on network calculus, we propose a technique for analyzing the communication delay bound for individual flows. The fundamental elements with the technique include three network calculus models that describe the traffic behaviors when flows are multiplexed, split, or controlled by feedback credits, respectively. Based on the basic models, we can compute the equivalent system service curve for individual flows and then calculate their packet delay bound.
|
|
| 7. |
|
|
| 8. |
- Qian, Yue, et al.
(författare)
-
From 2D to 3D NoCs : A Case Study of the worst-case Communication Performance
- 2009
-
Ingår i: IEEE/ACM 2009 International Conference on Computer-Aided Design (ICCAD’09). - : IEEE Computer Society. - 9781605588001 ; , s. 555-562
-
Konferensbidrag (refereegranskat)abstract
- Advanced integration technologies enable the construction of Network-on-Chip (NoC) from two dimensions to three dimensions. Studies have shown that 3D NoCs can improve average communication performance because of the possibility of using the additional dimension to shorten communication distance. In this paper, we present a detailed case study on worst-case communication performance in regular k-ary-2-mesh networks. Through both analysis and simulation, we show that, while 3D networks achieve better average performance, this may not be the case for worst-case performance mainly due to constraints on vertical channels. Our analysis is based on network calculus, which allows to calculate theoretical delay bounds for constrained flows traversing network elements.
|
|
| 9. |
- Qian, Yue, et al.
(författare)
-
Worst-Case Flit and Packet Delay Bounds in Wormhole Networks on Chip
- 2009
-
Ingår i: IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences. - 0916-8508 .- 1745-1337. ; E92A:12, s. 3211-3220
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate per-flow flit and packet worst-case delay bounds in on-chip wormhole networks. Such investigation is essential in order to provide guarantees under worst-case conditions in cost-constrained systems, as required by many hard real-time embedded applications. We first propose analysis models for flow control, link and buffer sharing. Based on these analysis models, we obtain an open-ended service analysis model capturing the combined effect of flow control, link and buffer sharing. With the service analysis model, we compute equivalent service curves for individual flows, and then derive their flit and packet delay bounds. Our experimental results verify that our analytical bounds are correct and tight.
|
|
